package com.leetcode.www;

import java.util.*;

/**
 * Creared with IntelliJ IDEA.
 * Description:字典wordList 中从单词 beginWord和 endWord 的 转换序列 是一个按下述规格形成的序列beginWord -> s1-> s2-> ... -> sk：
 *
 * 每一对相邻的单词只差一个字母。
 * 对于1 <= i <= k时，每个si都在wordList中。注意， beginWord不需要在wordList中。
 * sk== endWord
 * 给你两个单词 beginWord和 endWord 和一个字典 wordList ，返回 从beginWord 到endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0 。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/word-ladder
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * User:yxd
 * Date:2022-03-19
 * Time:17:21
 */
public class BFS127 {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        if(wordList.isEmpty())return 0;
        Set<String> set = new HashSet<>();//标记位
        set.add(beginWord);
        Queue<String> queue = new LinkedList<>();
        Set<String> di = new HashSet<>();//字典 方便查询
        for(String s:wordList){
            di.add(s);
        }
        queue.offer(beginWord);
        int count = 1;//开始的字符就算做一次了
        while(!queue.isEmpty()){
            int size = queue.size();
            while(size-- != 0){
                String s = queue.poll();
                for(int i = 0;i < s.length();i ++){
                    StringBuilder sb = new StringBuilder(s);
                    for(char c = 'a';c <= 'z';c++){
                        sb.setCharAt(i,c);//将i位置上的字符变成c字符
                        String w = sb.toString();
                        if(!di.contains(w) || set.contains(w)){//只要字典中没有或者已经使用过的就不需要入队了
                            continue;
                        }
                        if(w.equals(endWord)){
                            return count + 1;
                        }

                        queue.offer(w);//字典中有能转化到的单词就入队
                        set.add(w);//标记已使用


                    }
                }
            }
            count ++;

        }
        return 0;//所有的搜索走完了还没有的话就表明不能转换到最终字符
    }
}
